#include <assert.h>
#include <stdio.h>
#include "dig.h"

#define PATH_ADD_LAYER_PENALTY 20
#define BREACH_CANDIDATE_MAX 128
#define TUNNEL_LENGTH_MAX 32
#define DIGSTACK_SIZE 1024 // enough for 256x256 map
#define FLOODFILL_SEARCH_MAX 1024

// --- for astar_path ---
typedef struct {
	coord_t path [TUNNEL_LENGTH_MAX];
	int path_size;
	coord_t next; // the PathOption we consider is to append this coord to the existing path
	int cost; // estimate
} PathOption;

RectList* tilerect = NULL;
Map* map = NULL;
PathOption* dig_stack = NULL;
PathOption* temp_stack = NULL;
int ds_size = 0;
int ts_size = 0;

inline int dist (coord_t c1, coord_t c2);
void resize_data (); // call this after the map size has changed to properly resize tilerect and tile_mark. Array contents are not changed or initialized!!
void tilerect_clear (int z); // reset the tilerects on a layer to match an empty map
const Rect* find_room_container (int width, int height, coord_t near); // Find a tilerect near the coords that is big enough to contain the specified room
Rect align_room (const Rect* container, int width, int height, coord_t near); // Inside the specified tilerect, find an alignment for the specified room near another location
void place_room (Rect area); // Does the actual tile modifications on the map to create an empty room
int find_breach_walls (coord_t start, int (*is_room) (coord_t), coord_t* candidates, int my_mark); // finds candidate exits out of the area surrounding start (wall tiles only)
int is_breachable_wall (coord_t c); // returns whether or not the wall located at (c) can be dug through to create a tunnel
void nearest_pair (const coord_t* set1, int nset1, const coord_t* set2, int nset2, coord_t* first, coord_t* second); // Tries to find the nearest pair of walls from 2 sets
int astar_path (coord_t from, coord_t to, coord_t* pathbuf, int* length); // Finds a valid tunnel path, returns zero on success, nonzero if no connection could be found
int is_diggable (PathOption* o, coord_t from, coord_t to); // Returns whether or not po is a valid PathOption
void dig_path (const coord_t* path, int length); // Place the actual tunnel tiles
void make_teleporter (coord_t c1, coord_t c2); // Place a bidirectional teleporter

// prepares the dig module for an empty map with a single tile layer.
void dig_init (Map* m) 
{
	assert (m->num_layers == 1);
	dig_cleanup (); // to be safe: remove previous traces
	map = m;
	dig_stack = malloc (DIGSTACK_SIZE * sizeof(PathOption));
	temp_stack = malloc (DIGSTACK_SIZE * sizeof(PathOption));
	resize_data ();
	tilerect_clear (0);
	map_unmark_tiles (map);
}

void dig_cleanup ()
{
	free (tilerect);     tilerect = NULL;
	free (dig_stack);   dig_stack = NULL;
	free (temp_stack); temp_stack = NULL;
	map = NULL;
	ds_size = 0;
	ts_size = 0;
}

Rect dig_room (int width, int height, coord_t near)
{
	const Rect* container = find_room_container (width, height, near);
	Rect r = align_room (container, width, height, near);
	place_room (r);
	return r;
}

void dig_tunnel (coord_t from, coord_t to, int (*is_room) (coord_t))
{
	// first step: look for candidate walls out of the from- and to-areas
	coord_t walls1 [BREACH_CANDIDATE_MAX];
	coord_t walls2 [BREACH_CANDIDATE_MAX];
	int num_walls1 = find_breach_walls (from, is_room, walls1, 1);
	int num_walls2 = find_breach_walls (to  , is_room, walls2, 2);
	map_unmark_tiles (map);
	
	if (num_walls2 == -1) return; // already connected
	
	coord_t breach_from = from;
	coord_t breach_to = to;
	
	// Give a good suggestion for a direction for the nearest wall,
	// yet prevent it from being chosen as the final wall candidate
	int from_to_x = to.x - from.x;
	int from_to_y = to.y - from.y;
	if ((from_to_x == 0) && (from_to_y == 0)) {
		breach_from = walls1[0];
		breach_to   = walls2[0];
	} else {
		breach_from.x -= 1000 * from_to_x;
		breach_from.y -= 1000 * from_to_y;
		breach_to.x += 1000 * from_to_x;
		breach_to.y += 1000 * from_to_y;
	}
	
	if (num_walls1 > 0 && num_walls2 > 0) {
		nearest_pair(walls1, num_walls1, walls2, num_walls2, &breach_from, &breach_to);
	} else {
		fprintf (stderr, "[warn] Couldn't dig tunnel (%d,%d,%d) -> (%d,%d,%d), couldn't find enough \"breach walls\"\n", from.x, from.y, from.z, to.x, to.y, to.z);
		return;
	}
	
	coord_t path [TUNNEL_LENGTH_MAX];
	int length;
	if (astar_path (breach_from, breach_to, path, &length) == 0) {
		dig_path (path, length);
	} else {
		make_teleporter (breach_from, breach_to);
	}
}

inline int dist (coord_t c1, coord_t c2) { return abs(c2.x-c1.x) + abs(c2.y-c1.y) + abs(c2.z-c1.z); }

void resize_data ()
{
	tilerect = realloc (tilerect, map->width * map->height * map->num_layers * sizeof (RectList));
}

void tilerect_clear (int z)
{
	assert ((z >= 0) && (z < map->num_layers));
	RectList* list = tilerect + z * map->width * map->height;
	for (int y = 0; y < map->height; y++) 
	for (int x = 0; x < map->width; x++) {
		list->rect[0] = (Rect) { 0, 0, map->width, map->height, z };
		list->num_rects = 1;
		list++;
	}
}

const Rect* find_room_container (int width, int height, coord_t near)
{
	assert ((width <= map->width) && (height <= map->height)); // Success must be theoretically possible
	
	#define SEARCH_QUEUE_SIZE 512
	coord_t search_queue [SEARCH_QUEUE_SIZE];
	int q_begin;
	int q_end;
	
	for (int searchz = near.z; searchz < map->num_layers; searchz++) {
		q_begin = 0;
		q_end = 1;
		search_queue[0] = near;
		
		while (q_begin != q_end) {
			int searchx = search_queue[q_begin % SEARCH_QUEUE_SIZE].x;
			int searchy = search_queue[q_begin++ % SEARCH_QUEUE_SIZE].y;
			int index = map_index(map, searchx, searchy, searchz); // index of this square, to be analyzed now
			
			if (tilerect[index].num_rects > 0) { // if we are not in a room
				const Rect* r = tilerect[index].rect;
				if (((r->right - r->left) >= width) && ((r->bottom - r->top) >= height)) {
					map_unmark_tiles (map);
					return tilerect[index].rect;
				}
			}
			
			inline void add_search (int x, int y, int z) 
			{ 
				int i = map_index(map, x, y, z); 
				if (map->tile_mark[i] == 0) { 
					map->tile_mark[i] = 1;
					search_queue[q_end++ % SEARCH_QUEUE_SIZE] = (coord_t) {x,y,z};
					assert ((q_end - q_begin) <= SEARCH_QUEUE_SIZE);
				} 
			}
			
			if (searchx >= width)             add_search (searchx-width,  searchy, searchz);
			if (searchx < map->width-width)   add_search (searchx+width,  searchy, searchz);
			if (searchy >= height)            add_search (searchx, searchy-height, searchz);
			if (searchy < map->height-height) add_search (searchx, searchy+height, searchz);
		}
	}
	
	// nothing found, get another layer and try again. 
	// This time success is guaranteed (fresh layer).
	map_extend (map, map->num_layers);
	resize_data ();
	map_unmark_tiles (map);
	tilerect_clear (map->num_layers-1);
	return tilerect[map_index(map,0,0,map->num_layers-1)].rect;
	#undef SEARCH_QUEUE_SIZE
}

Rect align_room (const Rect* container, int width, int height, coord_t near)
{
	int room_center_min_x = container->left + width/2;
	int room_center_max_x = container->right - width/2 - width%2;
	int room_center_min_y = container->top + height/2;
	int room_center_max_y = container->bottom - height/2 - height%2;
	int room_center_x = MIN ( MAX (room_center_min_x, near.x), room_center_max_x );
	int room_center_y = MIN ( MAX (room_center_min_y, near.y), room_center_max_y );
	return (Rect) { room_center_x - width/2, room_center_y - height/2, 
		room_center_x + width/2 + width%2, room_center_y + height/2 + height%2, container->z };
}

void place_room (Rect area)
{
	assert ((area.left >= 0) && (area.right <= map->width));
	assert ((area.top >= 0) && (area.bottom <= map->height));
	assert (area.z < map->num_layers);
	
	for (int y = area.top ; y < area.bottom; y++)
	for (int x = area.left; x < area.right ; x++) {
		int index = map_index (map, x, y, area.z);
		map->tile[index].type = TILE_FLOOR;
		tilerect[index].num_rects = 0; // no more tilerects here
	}
	
	for (int y = area.top; y < area.bottom; y++) {
		map_tile(map, area.left   , y, area.z)->type = TILE_WALL;
		map_tile(map, area.right-1, y, area.z)->type = TILE_WALL;
	}
	for (int x = area.left+1; x < area.right-1; x++) {
		map_tile(map, x, area.top     , area.z)->type = TILE_WALL;
		map_tile(map, x, area.bottom-1, area.z)->type = TILE_WALL;
	}
	
	// Modify area for cutting into tilerects everywhere.
	// We enlarge it so there will be lots of space for corridors
	// all around.
	area.left -= 3;
	area.right += 3;
	area.top -= 3;
	area.bottom += 3;
	
	for (int y = 0; y < map->height; y++)
	for (int x = 0; x < map->width; x++) {
		int i = map_index(map, x, y, area.z);
		cut_all_rects (&tilerect[i], &area, x, y);
	}
}

#if TOWERHACK_DEBUG_DUNGEON_ANIM
extern void clear_highlighter ();
extern void highlight (int x, int y, int z, int r, int g, int b);
extern void highlight_r (Rect r, int red, int g, int blu);
extern void snapshot (Map* m);
#endif

// Return values:
// -1: while searching, a tile_mark != my_mark was encountered.
// >= 0: number of candidate walls that have been found
int find_breach_walls (coord_t start, int (*is_room) (coord_t), coord_t* candidates, int my_mark)
{
	coord_t* candidate_ptr = candidates;
	#define SEARCH_QUEUE_SIZE 512
	coord_t search_queue [SEARCH_QUEUE_SIZE];
	int q_begin = 0;
	int q_end = 1;
	search_queue[0] = start;
	int ffcount = FLOODFILL_SEARCH_MAX;
	assert (my_mark != 0);
	
	while ((q_begin != q_end) && (ffcount-- > 0)) {
		coord_t c = search_queue[q_begin++ % SEARCH_QUEUE_SIZE];
		int index = map_index(map, c.x, c.y, c.z); // index of this square, to be analyzed now
		
		#if TOWERHACK_DEBUG_DUNGEON_ANIM
		highlight (c.x,c.y,c.z, 150, 150, 0);
		snapshot (map);
		#endif 
		
		if (is_room(c)) continue; // Do not proceed search into protected rooms
		if (map->tile[index].type == TILE_WALL) {
			if (is_breachable_wall(c)) {
		#if TOWERHACK_DEBUG_DUNGEON_ANIM
		highlight (c.x,c.y,c.z, 250, 0, 0);
		snapshot (map);
		#endif 
				*candidate_ptr++ = c;
				if ((candidate_ptr - candidates) >= BREACH_CANDIDATE_MAX) break; // we've gathered enough
			}
			continue;
		}
		
		TileType tiletype = map->tile[index].type;
		assert (
			(tiletype == TILE_FLOOR) ||
			(tiletype == TILE_EXIT_BETWEEN) ||
			(tiletype == TILE_EXIT_DOWN) ||
			(tiletype == TILE_EXIT_UP) ||
			(tiletype == TILE_TELEPORTER)
		); // This is supposed to be clean SEGMENT_CORRIDOR territory. 
		
		int add_search (coord_t C) 
		{
			int index = map_index(map, (C).x, (C).y, (C).z);
			int mark = map->tile_mark[index]; 
			if (mark == 0) { 
				map->tile_mark[index] = my_mark;
				search_queue[q_end++ % SEARCH_QUEUE_SIZE] = (C); 
				#if TOWERHACK_DEBUG_DUNGEON_ANIM
				highlight (c.x,c.y,c.z, 0, 0, 170); 
				snapshot (map); 
				#endif 
				assert ((q_end - q_begin) <= SEARCH_QUEUE_SIZE); 
			} else 
			if (mark != my_mark) return 0;
			return 1;
		}
		
		if (tiletype == TILE_TELEPORTER) c = map_tile(map,c.x,c.y,c.z)->teleporter.target;
		if (c.x > 1)             { c.x--; if (!add_search(c)) return -1; c.x++; }
		if (c.x < map->width -2) { c.x++; if (!add_search(c)) return -1; c.x--; }
		if (c.y > 1)             { c.y--; if (!add_search(c)) return -1; c.y++; }
		if (c.y < map->height-2) { c.y++; if (!add_search(c)) return -1; c.y--; }
		if ((tiletype == TILE_EXIT_DOWN) || (tiletype == TILE_EXIT_BETWEEN)) { c.z--; if (!add_search(c)) return -1; c.z++; }
		if ((tiletype == TILE_EXIT_UP  ) || (tiletype == TILE_EXIT_BETWEEN)) { c.z++; if (!add_search(c)) return -1; c.z--; }
	}
	
				#if TOWERHACK_DEBUG_DUNGEON_ANIM
				clear_highlighter ();
	if ((candidate_ptr - candidates) <= 0) {
		fprintf (stderr, "crash! num_walls: %d\n", candidate_ptr - candidates);
				highlight (start.x,start.y,start.z, 255, 0, 0); 
				snapshot (map); 
				sleep (10);
			}
				#endif 
	assert (candidate_ptr - candidates > 0);
	return candidate_ptr - candidates;
}

// returns whether or not the wall located at (c) can be dug through to create a tunnel
int is_breachable_wall (coord_t c) 
{
	assert (map_tile(map, c.x, c.y, c.z)->type == TILE_WALL);
	assert ((c.z >= 0) && (c.z < map->num_layers));
	if ((c.x <= 0) || (c.x >= map->width-1) || (c.y <= 0) || (c.y >= map->height-1)) return 0;
	TileType n  = map_tile(map, c.x  , c.y-1, c.z)->type;
	TileType w  = map_tile(map, c.x-1, c.y  , c.z)->type;
	TileType e  = map_tile(map, c.x+1, c.y  , c.z)->type;
	TileType s  = map_tile(map, c.x  , c.y+1, c.z)->type;
	return (
		// Variation 1: digging north is possible
		(((n == TILE_UNDEFINED) || (n == TILE_WALL)) && (w == TILE_WALL) && (e == TILE_WALL) && (s == TILE_FLOOR)) ||
		// Variation 1: digging south is possible
		(((s == TILE_UNDEFINED) || (s == TILE_WALL)) && (w == TILE_WALL) && (e == TILE_WALL) && (n == TILE_FLOOR)) ||
		// Variation 1: digging west is possible
		(((w == TILE_UNDEFINED) || (w == TILE_WALL)) && (n == TILE_WALL) && (s == TILE_WALL) && (e == TILE_FLOOR)) ||
		// Variation 1: digging east is possible
		(((e == TILE_UNDEFINED) || (e == TILE_WALL)) && (n == TILE_WALL) && (s == TILE_WALL) && (w == TILE_FLOOR))
	);
}

void nearest_pair (const coord_t* set1, int nset1, const coord_t* set2, int nset2, coord_t* first, coord_t* second)
{
	assert ((nset1 > 0) && (nset2 > 0));
	int first_changed = 1;
	int second_changed = 1;
			
	while (first_changed || second_changed) {
		if (second_changed) {
			second_changed = 0;
			int min_dist = dist (*first, *second);
			for (int i = 0; i < nset1; i++) {
				int new_dist = dist (set1[i], *second);
				if (new_dist < min_dist) {
					min_dist = new_dist;
					*first = set1[i];
					first_changed = 1;
				}
			}
		}
		if (first_changed) {
			first_changed = 0;
			int min_dist = dist (*first, *second);
			for (int i = 0; i < nset2; i++) {
				int new_dist = dist (*first, set2[i]);
				if (new_dist < min_dist) {
					min_dist = new_dist;
					*second = set2[i];
					second_changed = 1;
				}
			}
		}
	}
}

int astar_path (coord_t from, coord_t to, coord_t* pathbuf, int* length)
{
	dig_stack[0] = (PathOption) { {}, 0, from, 0 };
	ds_size = 1;
	ts_size = 0;
	map->tile_mark[map_index(map,from.x,from.y,from.z)] = 1;
		
	inline PathOption* pop_stack () { assert(ds_size > 0); return &dig_stack [--ds_size]; }
	inline void push_stack (const PathOption* o) { assert(ds_size < DIGSTACK_SIZE); dig_stack [ds_size++] = *o; }
	inline coord_t pop_path (PathOption* o) { assert(o->path_size > 0); return o->path[--o->path_size]; }
	inline void push_path (PathOption* o, coord_t c) { assert(o->path_size < TUNNEL_LENGTH_MAX); o->path [o->path_size++] = c; }
	
	inline int cost (PathOption* po) { return po->path_size + dist (po->next, to) + ((po->next.z == map->num_layers) ? PATH_ADD_LAYER_PENALTY : 0); }
	
	while (ds_size > 0) {
		PathOption* option = pop_stack ();
		assert (option->next.z <= map->num_layers);
		
		push_path (option, option->next);
		if (dist(option->next, to) == 0) { 
			memcpy (pathbuf, option->path, option->path_size * sizeof(coord_t));
			*length = option->path_size;
			map_unmark_tiles (map);
			return 0; 
		}
		if ((option->path_size + dist(option->next, to)) >= TUNNEL_LENGTH_MAX) continue;
		
		PathOption add_pool [6] = { *option, *option, *option, *option, *option, *option };
		PathOption* add [6] = { &add_pool[0], &add_pool[1], &add_pool[2], &add_pool[3], &add_pool[4], &add_pool[5] };
		
		add_pool[0].next.x--; add_pool[0].cost = cost (&add_pool[0]);
		add_pool[1].next.x++; add_pool[1].cost = cost (&add_pool[1]);
		add_pool[2].next.y--; add_pool[2].cost = cost (&add_pool[2]);
		add_pool[3].next.y++; add_pool[3].cost = cost (&add_pool[3]);
		add_pool[4].next.z--; add_pool[4].cost = cost (&add_pool[4]);
		add_pool[5].next.z++; add_pool[5].cost = cost (&add_pool[5]);
		
		int cost_compare (const void* po1, const void* po2) { return (*(PathOption**)po2)->cost - (*(PathOption**)po1)->cost; }
		qsort(add, 6, sizeof(PathOption*), &cost_compare);
			
		// Move all lower-cost PathOptions from the dig_stack to a temp_stack, then shuffle back in order
		int temp_stack_size = ds_size;
			
		inline PathOption* pop_tstack () { assert(ts_size > 0); return &temp_stack [--ts_size]; }
		inline void push_tstack (const PathOption* o) { assert(ts_size < temp_stack_size); temp_stack [ts_size++] = *o; }
		
		while ((ds_size > 0) && (dig_stack[ds_size-1].cost < add[0]->cost)) push_tstack (pop_stack ());
		
		int i = 0;
		while ((i < 6) || (ts_size > 0)) {
			if (ts_size <= 0) {
				if (is_diggable (add[i], from, to)) {
					int mi; // Map index: when examining the top layer, avoid passing out-of-bounds coords to map_index()
					if (add[i]->next.z < map->num_layers) 
						mi = map_index (map, add[i]->next.x, add[i]->next.y, add[i]->next.z);
					else
						mi = map_index (map, add[i]->next.x, add[i]->next.y, add[i]->next.z-1) + map->width*map->height;
					if (map->tile_mark[mi] == 0) {
						map->tile_mark[mi] = 1; // mark visited
						push_stack (add[i]);
					}
				}
				i++;				
			} else 
			if (i >= 6) push_stack (pop_tstack ()); else
			if (temp_stack[ts_size-1].cost < add[i]->cost) {
				if (is_diggable (add[i], from, to)) {
					int mi;
					if (add[i]->next.z < map->num_layers) 
						mi = map_index (map, add[i]->next.x, add[i]->next.y, add[i]->next.z);
					else
						mi = map_index (map, add[i]->next.x, add[i]->next.y, add[i]->next.z-1) + map->width*map->height;
					if (map->tile_mark[mi] == 0) {
						map->tile_mark[mi] = 1; // mark visited
						push_stack (add[i]);
					}
				}
				i++;
			} else {
				push_stack (pop_tstack ());
			}
		}
		
		assert (ts_size == 0);
		assert (ds_size >= temp_stack_size);
	}
	
	// we found no connection
	map_unmark_tiles (map);
	return -1;
}

int is_diggable (PathOption* o, coord_t from, coord_t to)
{
	coord_t c = o->next;
	
	// Out of bounds?
	if ((c.x <= 0) || (c.y <= 0) || (c.z < 0) || 
		(c.x >= map->width-1) || (c.y >= map->height-1) || (c.z > map->num_layers)) return 0;

	// Can always dig in top layer
	if (c.z == map->num_layers) return 1;
	
	// Already visited?
	if (map->tile_mark[map_index(map, c.x, c.y, c.z)] == 1) return 0;
	
	int goal_dist = dist(c, to);
	if (goal_dist == 0) return 1;
	if (map_tile(map, c.x, c.y, c.z)->type != TILE_UNDEFINED) return 0;
	if ((c.z == to.z  ) && (goal_dist == 1)) return 1;
	if ((c.z == from.z) && (dist(c, from) == 1)) return 1;
	return (
		(map_tile(map, c.x-1, c.y, c.z)->type == TILE_UNDEFINED) &&
		(map_tile(map, c.x+1, c.y, c.z)->type == TILE_UNDEFINED) &&
		(map_tile(map, c.x, c.y-1, c.z)->type == TILE_UNDEFINED) &&
		(map_tile(map, c.x, c.y+1, c.z)->type == TILE_UNDEFINED)
	);
}

void dig_path (const coord_t* path, int length)
{
	Rect path_rects [TUNNEL_LENGTH_MAX];
	int num_path_rects = 0;
	Rect next_dig_rect = { 0, 0, 0, 0, 0 }; // needed to cut out tilerects in corridor area
	int last_z = path[0].z;
	
	inline int can_extend_rect (coord_t c) 
	{
		if (
			(next_dig_rect.z == c.z) &&
			(((next_dig_rect.right - next_dig_rect.left == 3) && (c.x == next_dig_rect.left+1)) ||
			((next_dig_rect.bottom - next_dig_rect.top == 3) && (c.y == next_dig_rect.top+1)))
		) return 1;
		else return 0;
	}
	inline void extend_rect (coord_t c) 
	{
		next_dig_rect.left = MIN(next_dig_rect.left, c.x-1);
		next_dig_rect.top = MIN(next_dig_rect.top, c.y-1);
		next_dig_rect.right = MAX(next_dig_rect.right, c.x+2);
		next_dig_rect.bottom = MAX(next_dig_rect.bottom, c.y+2);
	}
	
	for (int i = 0; i < length; i++) {
		coord_t c = path[i];
		if (c.z >= map->num_layers) {
			map_extend (map, c.z);
			resize_data ();
			tilerect_clear (c.z);
			map_unmark_tiles_layer (map, c.z);
		}
		if (map_tile(map, c.x  , c.y  , c.z)->type == TILE_WALL)      map_tile(map, c.x  , c.y  , c.z)->type = TILE_FLOOR;
		if (map_tile(map, c.x  , c.y-1, c.z)->type == TILE_UNDEFINED) map_tile(map, c.x  , c.y-1, c.z)->type = TILE_WALL;
		if (map_tile(map, c.x  , c.y+1, c.z)->type == TILE_UNDEFINED) map_tile(map, c.x  , c.y+1, c.z)->type = TILE_WALL;
		if (map_tile(map, c.x-1, c.y  , c.z)->type == TILE_UNDEFINED) map_tile(map, c.x-1, c.y  , c.z)->type = TILE_WALL;
		if (map_tile(map, c.x+1, c.y  , c.z)->type == TILE_UNDEFINED) map_tile(map, c.x+1, c.y  , c.z)->type = TILE_WALL;
		if (map_tile(map, c.x-1, c.y-1, c.z)->type == TILE_UNDEFINED) map_tile(map, c.x-1, c.y-1, c.z)->type = TILE_WALL;
		if (map_tile(map, c.x-1, c.y+1, c.z)->type == TILE_UNDEFINED) map_tile(map, c.x-1, c.y+1, c.z)->type = TILE_WALL;
		if (map_tile(map, c.x+1, c.y-1, c.z)->type == TILE_UNDEFINED) map_tile(map, c.x+1, c.y-1, c.z)->type = TILE_WALL;
		if (map_tile(map, c.x+1, c.y+1, c.z)->type == TILE_UNDEFINED) map_tile(map, c.x+1, c.y+1, c.z)->type = TILE_WALL;
		if (c.z < last_z) {
			if (map_tile(map, c.x, c.y, last_z)->type == TILE_EXIT_UP) {
				map_tile(map, c.x, c.y, last_z)->type = TILE_EXIT_BETWEEN;
			} else {
				map_tile(map, c.x, c.y, last_z)->type = TILE_EXIT_DOWN;
			}
			map_tile(map, c.x, c.y,    c.z)->type = TILE_EXIT_UP;
		}
		if (c.z > last_z) {
			if (map_tile(map, c.x, c.y, last_z)->type == TILE_EXIT_DOWN) {
				map_tile(map, c.x, c.y, last_z)->type = TILE_EXIT_BETWEEN;
			} else {
				map_tile(map, c.x, c.y, last_z)->type = TILE_EXIT_UP;
			}
			map_tile(map, c.x, c.y,    c.z)->type = TILE_EXIT_DOWN;
		}
		last_z = c.z;
		
		if (can_extend_rect (c)) extend_rect (c);
		else {
			path_rects[num_path_rects++] = next_dig_rect;
			next_dig_rect = (Rect) { c.x-1, c.y-1, c.x+2, c.y+2, c.z };
		}
	}
	path_rects[num_path_rects++] = next_dig_rect;
	
	for (int y = 0; y < map->height; y++)
	for (int x = 0; x < map->width ; x++) 
	for (int i = 1; i < num_path_rects; i++) {
		cut_all_rects (&tilerect[map_index(map,x,y,path_rects[i].z)], &path_rects[i], x, y);
	}
}

void make_teleporter (coord_t c1, coord_t c2)
{
	map_tile(map, c1.x, c1.y, c1.z)->type = TILE_TELEPORTER;
	map_tile(map, c1.x, c1.y, c1.z)->teleporter.target = c2;
	if (map_tile(map, c1.x  , c1.y-1, c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x  , c1.y-1, c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x  , c1.y+1, c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x  , c1.y+1, c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x-1, c1.y  , c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x-1, c1.y  , c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x+1, c1.y  , c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x+1, c1.y  , c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x-1, c1.y-1, c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x-1, c1.y-1, c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x-1, c1.y+1, c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x-1, c1.y+1, c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x+1, c1.y-1, c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x+1, c1.y-1, c1.z)->type = TILE_WALL;
	if (map_tile(map, c1.x+1, c1.y+1, c1.z)->type == TILE_UNDEFINED) map_tile(map, c1.x+1, c1.y+1, c1.z)->type = TILE_WALL;
	
	map_tile(map, c2.x, c2.y, c2.z)->type = TILE_TELEPORTER;
	map_tile(map, c2.x, c2.y, c2.z)->teleporter.target = c1;
	if (map_tile(map, c2.x  , c2.y-1, c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x  , c2.y-1, c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x  , c2.y+1, c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x  , c2.y+1, c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x-1, c2.y  , c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x-1, c2.y  , c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x+1, c2.y  , c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x+1, c2.y  , c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x-1, c2.y-1, c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x-1, c2.y-1, c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x-1, c2.y+1, c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x-1, c2.y+1, c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x+1, c2.y-1, c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x+1, c2.y-1, c2.z)->type = TILE_WALL;
	if (map_tile(map, c2.x+1, c2.y+1, c2.z)->type == TILE_UNDEFINED) map_tile(map, c2.x+1, c2.y+1, c2.z)->type = TILE_WALL;
}
